/*
 ------------------------------------------------------------------------------
 Copyright (C) 2006-2007 Team Blur.

 This file is part of the Quantum Engine source code.

 The Quantum Engine source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The Quantum Engine source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the Quantum Engine source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


#include "r_local.h"


/*
 ==================
 R_QSortDrawMeshes
 ==================
*/
static void R_QSortDrawMeshes (int numDrawMeshes, drawMesh_t *drawMeshes){

	drawMesh_t	tmp;
	int			stack[4096];
	int			stackDepth = 0;
	int			L, R, l, r, median;
	uint		pivot;

	if (numDrawMeshes < 2)
		return;

	L = 0;
	R = numDrawMeshes - 1;

recurse:
	l = L;
	r = R;

	median = (l + r) >> 1;

	if (drawMeshes[l].sort > drawMeshes[median].sort){
		if (drawMeshes[l].sort < drawMeshes[r].sort) 
			median = l;
	} 
	else if (drawMeshes[r].sort < drawMeshes[median].sort)
		median = r;

	pivot = drawMeshes[median].sort;

	while (l < r){
		while (drawMeshes[l].sort < pivot)
			l++;
		while (drawMeshes[r].sort > pivot)
			r--;

		if (l <= r){
			tmp = drawMeshes[r];
			drawMeshes[r] = drawMeshes[l];
			drawMeshes[l] = tmp;

			l++;
			r--;
		}
	}

	if ((L < r) && (stackDepth < 4096)){
		stack[stackDepth++] = l;
		stack[stackDepth++] = R;
		R = r;
		goto recurse;
	}

	if (l < R){
		L = l;
		goto recurse;
	}

	if (stackDepth){
		R = stack[--stackDepth];
		L = stack[--stackDepth];
		goto recurse;
	}
}

/*
 ==================
 R_SortDrawMeshes
 ==================
*/
void R_SortDrawMeshes (void){

	drawLight_t	*drawLight;
	int			i;

	// Set up viewParms
	tr.viewParms.numDrawMeshes = tr.view.numDrawMeshes - tr.view.firstDrawMesh;
	tr.viewParms.numDrawPostProcessMeshes = tr.view.numDrawPostProcessMeshes - tr.view.firstDrawPostProcessMesh;

	tr.viewParms.numDrawLights = tr.view.numDrawLights - tr.view.firstDrawLight;
	tr.viewParms.numDrawFogLights = tr.view.numDrawFogLights - tr.view.firstDrawFogLight;

	// Sort
	R_QSortDrawMeshes(tr.viewParms.numDrawMeshes, tr.viewParms.drawMeshes);
	R_QSortDrawMeshes(tr.viewParms.numDrawPostProcessMeshes, tr.viewParms.drawPostProcessMeshes);

	for (i = 0, drawLight = tr.viewParms.drawLights; i < tr.viewParms.numDrawLights; i++, drawLight++){
		R_QSortDrawMeshes(drawLight->numInteractionMeshes[0], drawLight->interactionMeshes[0]);
		R_QSortDrawMeshes(drawLight->numInteractionMeshes[1], drawLight->interactionMeshes[1]);

		R_QSortDrawMeshes(drawLight->numShadowMeshes[0], drawLight->shadowMeshes[0]);
		R_QSortDrawMeshes(drawLight->numShadowMeshes[1], drawLight->shadowMeshes[1]);
	}

	for (i = 0, drawLight = tr.viewParms.drawFogLights; i < tr.viewParms.numDrawFogLights; i++, drawLight++)
		R_QSortDrawMeshes(drawLight->numInteractionMeshes[0], drawLight->interactionMeshes[0]);
}

/*
 ==================
 R_AddDrawMesh
 ==================
*/
void R_AddDrawMesh (meshType_t type, mesh_t *mesh, material_t *material, entity_t *entity){

	drawMesh_t	*drawMesh;

	tr.pc.meshes++;

	if (material->sort != SORT_POST_PROCESS){
		if (tr.view.numDrawMeshes == MAX_DRAW_MESHES){
			Com_DPrintf(S_COLOR_YELLOW "R_AddDrawMesh: MAX_DRAW_MESHES hit\n");
			return;
		}

		drawMesh = &tr.view.drawMeshes[tr.view.numDrawMeshes++];
	}
	else {
		if (tr.view.numDrawPostProcessMeshes == MAX_DRAW_POST_PROCESS_MESHES){
			Com_DPrintf(S_COLOR_YELLOW "R_AddDrawMesh: MAX_DRAW_POST_PROCESS_MESHES hit\n");
			return;
		}

		drawMesh = &tr.view.drawPostProcessMeshes[tr.view.numDrawPostProcessMeshes++];
	}

	drawMesh->sort = (material->index << SORT_SHIFT_MATERIAL) | (entity->index << SORT_SHIFT_ENTITY) | (type << SORT_SHIFT_TYPE);
	drawMesh->mesh = mesh;
}

/*
 ==================
 R_DecomposeSort
 ==================
*/
void R_DecomposeSort (scene_t *scene, uint sort, material_t **material, entity_t **entity, meshType_t *type, bool *caps){

	*material = tr.sortedMaterials[(sort >> SORT_SHIFT_MATERIAL) & (MAX_MATERIALS-1)];
	*entity = &scene->entities[(sort >> SORT_SHIFT_ENTITY) & (MAX_RENDER_ENTITIES-1)];
	*type = (meshType_t)((sort >> SORT_SHIFT_TYPE) & 15);
	*caps = sort & 1;
}
